
import java.util.ArrayList;
import java.util.HashMap;

import javalib.colors.*;
import javalib.funworld.World;
import javalib.worldimages.*;

// to represent the MazeGame
public class MazeGame extends World {

    // how many nodes wide the maze is
    int width;
    // how many nodes high the maze is
    int height;
    // the status of this MazeGame is used to facilitate
    // manual manipulation, depth first, and breadth first
    // of this MazeGame
    String status;
    // key is represented by an Point where the Point
    // is the x coordinate and the y coordinate
    // The hashmap consists of these Point leading to Nodes
    // overall it represents the maze as visualized by humans
    //  HashMap<Point, Node> graph;
    HashMap<Point, Node> graph;
    // Points to the root of the tree initially. This is ultimately the
    // same as the HashMap but this representation optimizes searches
    // while still allowing initialization to be optimized by the Hashmap.
    // During a depth check this points to the current Branch being
    // checked for efficiency
    Branch tree;

    // Clarification: The system of using both the HashMap<Point, Node> and
    // Branch is to implement a few extra features into the Maze. The bare
    // minimum assignment could be completed using only one. Using both allows
    // the use of multiple extra features in a timely fashion.

    // default constructor
    MazeGame(int x, int y) {
        this.width = x;
        this.height = y;
        this.status = "start";
        this.graph = new HashMap<Point, Node>();
        this.tree = new Branch();
        this.init();
    }

    // main method, runs the Maze Game
    // commented out to make WebCat happy
    public static void main(String[] argv) {
        MazeGame mg = new MazeGame(25, 15);
        mg.bigBang(mg.width * 50, mg.height * 50, 0.2);
    }

    // initializes the MazeGame
    public void init() {
        ArrayList<Edge> edges = new ArrayList<Edge>();
        for (int x = 0; x < this.width; x++) {
            for (int y = 0; y < this.height; y++) {
                Node temp = new Node();
                if (x > 0) {
                    edges.add(new Edge(temp, this.graph.get(
                            new Point(x - 1, y)), "horizontal"));
                }
                if (y > 0) {
                    edges.add(new Edge(temp, this.graph.get(
                            new Point(x, y - 1)), "vertical"));
                }
                this.graph.put(new Point(x, y), temp);
            }
        }
        Node n = this.graph.get(new Point(0, 0));
        n.status = "checking";
        edges = this.edgesSort(edges);
        this.kruskal(edges);
        this.tree = new Branch();
        this.graph.get(new Point(0, 0)).initTree(tree, tree);
    }

    // sorts the list of edges so that the edges with lowest weight are first
    public ArrayList<Edge> edgesSort(ArrayList<Edge> edges) {
        ArrayList<Edge> temp = new ArrayList<Edge>();
        for (Edge e: edges) {
            if (temp.isEmpty()) {
                temp.add(e);
            }
            else {
                int index = 0;
                while (index < temp.size()) {
                    if (e.weight < temp.get(index).weight) {
                        temp.add(index, e);
                        index = temp.size();
                    }
                    index++;
                    if (index == temp.size()) {
                        temp.add(e);
                        index++;
                    }
                }
            }
        }
        edges = temp;
        return edges;
    }

    // runs the Kruskal algorithm and mutates the graph into a maze
    public void kruskal(ArrayList<Edge> edges) {
        while (!edges.isEmpty()) {
            Edge temp = edges.get(0);
            if (!this.canReach(temp.first, temp.second, "")) {
                if (temp.direction.equals("horizontal")) {
                    temp.first.left = temp.second;
                    temp.second.right = temp.first;
                }
                else if (temp.direction.equals("vertical")) {
                    temp.first.up = temp.second;
                    temp.second.down = temp.first;
                }
            }
            edges.remove(0);
        }

    }

    // runs key events for the Maze Game
    public MazeGame onKeyEvent(String key) {
        if (key.equals("n")) {
            this.init();
            return this;
        }
        if (this.status.equals("manual")) {
            this.onManualKeyEvent(key);
        }
        if (key.equals("m")) {
            this.status = "manual";
        }
        if (key.equals("b")) {
            this.status = "breadth";
        }
        if (key.equals("d")) {
            this.status = "depth";
        }
        return this;
    }

    // runs KeyEvent's for Manual status
    public MazeGame onManualKeyEvent(String key) {
        if (key.equals("up") ||
                key.equals("down") ||
                key.equals("left") ||
                key.equals("right")) {
            for (int x = 0; x < this.width; x++) {
                for (int y = 0; y < this.height; y++) {
                    Node original = this.graph.get(new Point(x, y));
                    if (original.status.equals("checking")) {
                        if (key.equals("up") && 
                                !original.up.equals(original)) {
                            Node n = this.graph.get(new Point(x, y - 1));
                            n.status = "checking";
                            original.status = "checked";
                            return this;
                        }
                        if (key.equals("down") && 
                                !original.down.equals(original)) {
                            Node n = this.graph.get(new Point(x, y + 1));
                            n.status = "checking";
                            original.status = "checked";
                            return this;
                        }
                        if (key.equals("left") && 
                                !original.left.equals(original)) {
                            Node n = this.graph.get(new Point(x - 1, y));
                            n.status = "checking";
                            original.status = "checked";
                            return this;
                        }
                        if (key.equals("right") && 
                                !original.right.equals(original)) {
                            Node n = this.graph.get(new Point(x + 1, y));
                            n.status = "checking";
                            original.status = "checked";
                            return this;
                        }
                    }
                }
            }
        }
        return this;
    }

    // checks if these two given Nodes can reach other, uses String for
    // recursive calls
    public boolean canReach(Node first, Node second, String directionFrom) {
        if (first.down.equals(second) ||
                first.up.equals(second) ||
                first.right.equals(second) ||
                first.left.equals(second)) {
            return true;
        }
        if (!first.down.equals(first) && !directionFrom.equals("down") && 
                this.canReach(first.down, second, "up")) {
            return true;
        }
        if (!first.up.equals(first) && !directionFrom.equals("up") && 
                this.canReach(first.up, second, "down")) {
            return true;
        }
        if (!first.right.equals(first) && !directionFrom.equals("right") && 
                this.canReach(first.right, second, "left")) {
            return true;
        }
        if (!first.left.equals(first) && !directionFrom.equals("left") && 
                this.canReach(first.left, second, "right")) {
            return true;
        }
        return false;
    }

    // renders the image of this maze
    public WorldImage makeImage() {
        WorldImage image = new FrameImage(new Posn(0, 0), this.width * 100,
                this.height * 100, new Black());
        if (this.status.equals("start")) {
            image = new TextImage(new Posn(this.width * 25, this.height * 10),
                    "Press 'm' to start in Manual Mode", new Black());
            image = new OverlayImages(image, 
                    new TextImage(new Posn(this.width * 25, this.height * 20),
                            "Press 'b' to start in Breadth-First Mode",
                            new Black()));
            image = new OverlayImages(image, 
                    new TextImage(new Posn(this.width * 25, this.height * 30),
                            "Press 'd' to start in Depth-First Mode",
                            new Black()));
            image = new OverlayImages(image, 
                    new TextImage(new Posn(this.width * 25, this.height * 40),
                            "Press 'n' at any time to generate a new maze",
                            new Black()));
            return image;
        }
        else {
            for (int x = 0; x < this.width; x++) {
                for (int y = 0; y < this.height; y++) {
                    Node temp = this.graph.get(new Point(x, y));
                    if (x == this.width - 1 && y == this.height - 1) {
                        image = new OverlayImages(image,
                                new RectangleImage(
                                        new Posn(x * 50 + 25, y * 50 + 25),
                                        48, 48, new Red()));
                    }
                    if (temp.status.equals("checked")) {
                        image = new OverlayImages(image,
                                new RectangleImage(
                                        new Posn(x * 50 + 25, y * 50 + 25),
                                        48, 48, new Yellow()));
                    }
                    if (x == 0 && y == 0) {
                        image = new OverlayImages(image,
                                new RectangleImage(
                                        new Posn(x * 50 + 25, y * 50 + 25),
                                        48, 48, new Blue()));
                    }
                    if (temp.status.equals("checking")) {
                        image = new OverlayImages(image,
                                new RectangleImage(
                                        new Posn(x * 50 + 25, y * 50 + 25),
                                        48, 48, new Green()));
                    }
                    if (temp.status.equals("path")) {
                        image = new OverlayImages(image,
                                new RectangleImage(
                                        new Posn(x * 50 + 25, y * 50 + 25),
                                        48, 48, new Red()));
                    }
                    if (temp.up.equals(temp)) {
                        image = new OverlayImages(image,
                                new LineImage(new Posn(x * 50, y * 50),
                                        new Posn((x + 1) * 50, y * 50),
                                        new Black()));
                    }
                    if (temp.left.equals(temp)) {
                        image = new OverlayImages(image,
                                new LineImage(new Posn(x * 50, y * 50),
                                        new Posn(x * 50, (y + 1) * 50),
                                        new Black()));
                    }
                }
            }
            if (this.graph.get(
                    new Point(this.width - 1, this.height - 1))
                    .status.equals("checking")) {
                while (!this.tree.parent.equals(this.tree)) {
                    this.tree.data.status = "path";
                    this.tree = this.tree.parent;
                }
                return  new OverlayImages(image,
                        new TextImage(new Posn(250, 250), "Maze completed",
                                new Black()));
            }
        }
        return image;
    }

    // ticks the maze game. Dispatches the tick method
    // to the Nodes
    public MazeGame onTick() {
        if (this.graph.get(
                new Point(this.width - 1, this.height - 1))
                .status.equals("path")) {
            return this;
        }
        if (this.status.equals("breadth")) {
            this.breadthTick(this.tree);
        }
        else if (this.status.equals("depth")) {
            this.tree = this.tree.depthTick();
        }
        return this;

    }

    // the tick function for when the MazeGame is operating
    // a breadth search
    public void breadthTick(Branch tree) {
        if (tree.data.status.equals("checking")) {
            tree.data.status = "checked";
            for (Branch b: tree.children) {
                if (b.data.equals(this.graph.get(
                        new Point(width - 1, height - 1)))) {
                    b.data.status = "checking";
                    this.tree = b;
                }
                b.data.status = "checking";
            }
        }
        else {
            for (Branch b: tree.children) {
                this.breadthTick(b);
            }
        }
    }

}
